package com.kevinkk.dp;

/**
 * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
 * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
 * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
 */

/**
 * 以前的01背包问题只有一个限制：重量，这道题里有两个限制：0 的数量最多为 m， 1 的数量最多为 n
 * 1. dp 数组的含义：dp[i][j] ：有 i 个 0 和 j 个 1 时最多的物品【数量】
 * 2. dp 公式：dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)
 *      要么不放置物品，那么数量不变，0 和 1 的数量也不变
 *      要么放置物品，那么数量加一，0 和 1 的数量做对应的减少
 * 3. 初始化：这还是一个01背包问题，只用初始化 dp[0][0] 即可
 * 4. 遍历顺序：先遍历物品，然后再逆序遍历背包
 *      但是在遍历背包时，有两个维度的条件！
 */

public class OnesAndZeroes {
    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m + 1][n + 1];

            for (String s : strs) {
                int zero = 0, one = 0;
                char[] cs = s.toCharArray();
                for (char c : cs) {
                    if (c == '0')
                        zero++;
                    if (c == '1')
                        one++;
                }

                for (int i = m; i >= zero; i--) {
                    for (int j = n; j >= one; j--) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
                    }
                }
            }

            return dp[m][n];
        }
    }
}
